package leetbook.tree;

import datastruct.tree.TreeNode;

/**
 * 树中节点的最近公共祖先
 */
public class Solution236 {

    /**
     * 根据以root为根节点的子树包含p,q的情况
     * 如果root是p或q且root的左右子树包含p或q，那么root即为所找
     * 如果root不是p或q，且root左子树和右子树各包含p或q，root也即为所找
     * 需要一个函数返回root树的左右子树包含p，q的情况
     * @param root
     * @param p
     * @param q
     * @return
     */
    TreeNode res = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        contains(root,p,q);
        return res;
    }

    public boolean contains(TreeNode root, TreeNode p, TreeNode q){
        if(root==null||res!=null) return false; //答案找到就可以不遍历了，直接剪枝
        boolean lcon = contains(root.left,p,q);
        boolean rcon = contains(root.right,p,q);
        if(lcon&&rcon) res = root;
        if((root==p||root==q)&&(lcon||rcon)) res = root;
        return root==p||root==q||lcon||rcon;
    }
}
